// Copyrights by Kenneth Lee, 2022. All Rights Reserved
//
// car24_v2:
// A Simpler algorithm for card24.
//
#include <iostream>
#include <assert.h>
#include "value.hpp"

using namespace std;

static Val target;

static void reduce(ValComp set[], int sz);

static void cal(ValComp *set, ValComp *sub_set, int sz, int i, int j, ValComp::OPS op) {
	// create sub-set without i and j
	int m = 0;
	for (int k = 0; k < sz; k ++) {
		if (k != i && k != j) {
			sub_set[m++] = set[k];
		}
	}
	assert(m == sz - 2); // the last space is kept for a combination
	sub_set[m].merge_op(&set[i], &set[j], op);
	sub_set[m].evaluate();
	reduce(sub_set, sz - 1);
}

static void reduce(ValComp set[], int sz) {
	if (sz == 1) {
		if (debug_level > 0 || set[0].ret == target) {
			set[0].show_expr();
			cout << " = " << set[0].ret << endl;
		}
	} else {
		ValComp *sub_set = new ValComp[sz - 1];
		for (int i = 0; i < sz - 1; i ++)
			for (int j = i + 1; j < sz; j ++) {
				for (int op = ValComp::ADD; op < ValComp::INV_OP; op++)
					cal(set, sub_set, sz, i, j, (ValComp::OPS)op);
				cal(set, sub_set, sz, j, i, ValComp::SUB);
				cal(set, sub_set, sz, j, i, ValComp::DIV);
			}
		delete []sub_set;
	}
}

int main(int argc, char *argv[]) {
	if (argc < 2)
		return -1;

	target = argv[1];
	int n_cards = argc - 2;
	ValComp *set = new ValComp[n_cards];
	for (int i = 0; i < n_cards; i++)
		set[i].ret = atoi(argv[i+2]);
	reduce(set, n_cards);
	delete []set;
	return 0;
}
